package Leetcode;


/**
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 */
public class test82 {

    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead=new ListNode();
        dummyHead.next=head;
        ListNode prev=dummyHead;
        ListNode fir=prev.next;
         while (fir!=null){
             ListNode sec=fir.next;
             if (sec==null){
                 //此时当前链表只有一个节点或者sec走到null，所有的节点判断完毕
                 break;
             } else{
                 //此时链表至少存在两个节点
                 if (fir.val!= sec.val){
                     prev=prev.next;
                     fir=fir.next;
                 }else{
                     //此时遇到了重复元素，一直移动sec
                     while(sec!=null&&fir.val== sec.val){
                         sec=sec.next;
                     }
                     //此时sec指向第一个不重复的节点
                     prev.next=sec;
                     fir=sec;
                 }
             }
         }return dummyHead.next;

    }

//    /**
//     * 使用递归思路
//     * @param head
//     * @return
//     */
//    public ListNode deleteDuplicates1(ListNode head) {
//        if (head==null||head.next==null){
//            return head;
//        }
//        if (head.val!=head.next.val){
//            //此时头节点不是待删除的节点
//            head.next=deleteDuplicates1(head.next);
//            return head;
//        }else{
//            ListNode newHead=head.next;
//            while(newHead!=null&&head.val==newHead.val){
//                newHead=newHead.next;
//            }
//            //此时，newHead一定不是待删除的头节点,交给函数去搞
//            return deleteDuplicates1(newHead);
//        }
//    }
}
